COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.cb NOTES ON THE MISSIONARIES AND CANNIBALS
C00012 ENDMK
C⊗;
.cb NOTES ON THE MISSIONARIES AND CANNIBALS


	The missionaries and cannibals problem has much in it for artificial
intelligence.  The first step, of course, was to treat it as a
search problem.  No doubt the very first programmer to program a
solution represented a state by a triplet giving the numbers of missionaries, 
cannibals and boats on the initial bank of the river.  There are
then only 32 potential states, not all of which are legal, and even
the simplest tree search program can quickly find the solution.
On need not speak of heuristic search; any search will do.

	Even at this level there may be a skeleton in the closet.
A careful examination will show that while the computer program
does little search, the human does less.  Since either search is
small enough to be completely examined, the problem may be worth
thinking about until computer programs are found that do no more
search than the human.  Of course, it is necessary to write the
program honestly, i.e. to put no more information in it than the
human would have, and before one can do that it may be necessary
to think hard about what constitutes honesty in this case.
Actually this paragraph was a digression, because I have nothing
to say about the heuristic aspects of the problem apart from the
above general words of wisdom.

	The next step in discussion of M&C was made by Amarel (1969),
who pointed out that one could consider various representations of
the problem.  One might, for example, give the individual missionaries
and cannibals names.  Then there would be 128 states, since
this representation distinguishes which individuals are on each
bank and doesn't merely count them.  Amarel concludes that the
counting representation is better since it leads to less search.

	The main question we shall consider is how one gets to
the representation from the English language statement of the
problem which we may express as follows:

	%2"Three missionaries and three cannibals come to a river.  A
rowboat that seats two is available.  However, if the cannibals ever
outnumber the missionaries on either bank of the river, the outnumbered
missionaries will be eaten.  How shall they cross the river?"%1.

	We would like a computer program that would read the above
English statement, apply its general knowledge, arrive at the
Amarel representation, solve the problem and report the results
in good English.  It should also be able to defend its solution
against attack and solve modified versions of the problem.

	Current fashion in AI would concentrate on the natural
language aspect of the problem.  This is is one part of the problem,
but let's enumerate all the important aspects we can find.

.item←0
	#. Clearly the problem involves common sense knowledge,
because the fact that boats can be used to cross rivers is
unstated in the problem.  Indeed, the even more basic facts about
situations and the effects of actions and other events in bringing
about new situations with desired properties are unstated in
the problem and must be part of common sense.  To see this more
clearly, contrast this kind of problem with the purely mathematical
problem of finding the smallest integer expressible as the sum of
two cubes in two different ways.  In the latter problem, there is
nothing about actions changing situations.  It is characteristic
of the AI habit of shoving under the rug aspects of reality not 
being considered at the moment that the term "problem solving" in
AI has come to mean the problem of bringing about a desired discrete
state of affairs by a sequence of actions in circumstances of
perfect information.

	#. We are tempted to express the problem in a first order
logic formalism.  There are many pitfalls, but here is a first attempt at such
a formalizaton.

	card M = 3
	card C = 3
	∀x.(x ε M ⊃ missionary x)
	∀x.(x ε C ⊃ cannibal x)
	∀x.(x ε M ∪ C ⊃ at(x,leftbank(River),S0))
	river(River)
	at(Boat,leftbank(River),S0)
	boat(Boat) ∧ capacity(Boat) = 2
	∀s bank.(bank ε α{leftbank(River),rightbank(River)α} ∧
card α{x ε C | at(x,bank,s)α} > card α{x ε M | at(x,bank,sα}
unacceptable(s))

	The problem is then to find %2strat%1 satisfying

	%2∀x.(x ε M∪C ⊃ at(x,rightbank(River),result(does(MuC,strat),S0)))%1.

	In the above, ⊗M is the set of missionaries present and ⊗C is the
set of cannibals.  The first two sentences say that each has three members.
The next two sentences say that the members of ⊗M and ⊗C are missionaries
and cannibals respectively.  The next sentence says that they are all at
the left bank of ⊗River in the initial situation ⊗S0.
We then assert that ⊗River is a river.  We are using a convention that
capitalized identifiers are proper names, i.e. identify individual
objects.  The next two sentences identify the boat as a boat, locate it
at the left bank and assert that its capacity is two.
The final sentence says that situations in which the missionaries outnumber
the cannibals on either bank are unacceptable.  Using the predicate
unacceptable avoids having to formalize the assertion that "the missionaries
will be eaten".  A complete solution would have to express that fact too.

	Any such translation must be criticized from two points of view.
First, we ask is it merely a translation of the problem from English or
have we sneaked in some idea of how we want the problem solved.  If the
latter, we are unlikely to get such a translation from
a mere program for translating English to first order logic - unless
the writer knew in advance that he was going to have to translate
the missionaries and cannibals problem.

	The second point of criticism is the adequacy of the translation
from the point of view of solving the problem.  Can a reasonable problem
solver equipped with a reasonable formal expression of common sense
knowledge find the required strategy?

	Unfortunately, the above translation is defective on both
counts.